//
// Description: 145. 二叉树的后序遍历
// Created by Loading on 2021/5/4.
//

#include <bits/stdc++.h>
#include "Data_Structure_Definition.h"

using namespace std;

/* 递归算法 */
void postorderInternal(vector<int> &res, TreeNode *root) {
    if (!root) {
        return;
    }
    postorderInternal(res, root->left);
    postorderInternal(res, root->right);
    res.emplace_back(root->val);
}

vector<int> postorderTraversal(TreeNode *root) {
    vector<int> res;
    postorderInternal(res, root);

    return res;
}

/* 迭代算法 */
vector<int> postorderTraversal_Iteratively(TreeNode *root) {
    vector<int> res;
    //维护一个栈
    stack<TreeNode *> stk;
    //pre节点，指向上一次遍历的节点，为了判断某个节点的左右子树是否全部遍历完毕
    TreeNode *pre = nullptr;
    /* 栈为空且root为nullptr，表示遍历完毕 */
    /* 栈为空，root不为nullptr，表示开始遍历根节点右子树 */
    /* 栈不为空，root为nullptr，表示遍历到叶子节点或此节点的左右子树均遍历完毕，继续搜索上级节点 */
    while (!stk.empty() || root) {
        //root及其左子树全部入栈
        while (root) {
            stk.emplace(root);
            root = root->left;
        }
        root = stk.top();

        //如果栈顶元素右子树为空，则为叶子节点，加入结果集
        //如果栈顶元素右子树为pre，则为左右子树均遍历完成的根节点，同样加入结果集
        if (!root->right || root->right == pre) {
            res.emplace_back(root->val);
            //pre指向root，表示上一次遍历的节点
            pre = root;
            //root置空，表示此节点遍历完毕，并在栈中弹出
            root = nullptr;
            stk.pop();
        } else {
            //还未遍历其右子树，则指向右子树
            root = root->right;
        }
    }

    return res;
}

int main() {
    auto *root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);

    //使用递归算法
    vector<int> res;
    res = postorderTraversal(root);
    for (auto &x : res) {
        cout << x << " ";
    }
    cout << endl;

    //使用迭代算法
    vector<int> res_iter;
    res_iter = postorderTraversal_Iteratively(root);
    for (auto &x : res_iter) {
        cout << x << " ";
    }
    cout << endl;
}